import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        //根节点为空则直接返回空
        if(root==null){
            return null;
        }
        //如果其中有一个根节点等于root，则最近公共祖先即为root
        if(root==p||root==q){
            return root;
        }
        //开始递归判断
        TreeNode leftTreeLowestCommonAncestor=lowestCommonAncestor1(root.left,p,q);
        TreeNode rightTreeLowestCommonAncestor=lowestCommonAncestor1(root.right,p,q);
        if(leftTreeLowestCommonAncestor!=null&&rightTreeLowestCommonAncestor!=null){
            //左右子树返回值都不为空，说明p与q分别位于根节点两侧， 根节点为最近公共祖先
            return root;
        }else if(leftTreeLowestCommonAncestor!=null){
            //左子树有最近公共祖先
            return leftTreeLowestCommonAncestor;
        }else{
            //右子树有最近公共祖先
            return rightTreeLowestCommonAncestor;
        }
    }
    public TreeNode lowestCommonAncestor2(TreeNode root,TreeNode p,TreeNode q){
        //根节点为空则直接返回
        if(root==null){
            return root;
        }
        //为两个指定节点分别创建两个存储其各自到根节点路径的栈
        Stack<TreeNode>stackp=new Stack<>();
        getPath(root,p,stackp);
        Stack<TreeNode>stackq=new Stack<>();
        getPath(root,p,stackq);
        //计算两个栈的大小并比较
        int sizep=stackp.size();
        int sizeq=stackq.size();
        //将较长的栈的元素出栈直到元素个数相等
        if(sizep>sizeq) {
            int size = sizep - sizeq;
            while (size != 0) {
                stackp.pop();
                size--;
            }
        }else{
                int size=sizeq-sizep;
                while(size!=0){
                    stackq.pop();
                    size--;
            }
        }
        //将剩余元素全部出栈直到寻找到相同的节点，此节点即为最近公共祖先
        while(!stackp.isEmpty()&&!stackq.isEmpty()){
            if(stackp.peek()==stackq.peek()){
                return stackp.peek();
            }else{
                stackp.pop();
                stackq.pop();
            }
        }
        return null;
    }
    //将指定节点到根节点的路径存放到指定栈的底层方法
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        //为空返回false
        if(root==null){
             return false;
         }
        //将根节点入栈
        stack.push(root);
        //根节点为指定节点则直接返回true
        if(root==node){
            return true;
        }
        //递归左子树，获取路径
        boolean leftFlg=getPath(root.left,node,stack);
        //成功获取到路径，直接返回标志true
        if(leftFlg==true){
            return true;
        }
        //递归右子树，获取路径
        boolean rightFlg=getPath(root.right,node,stack);
        //成功获取到路径，直接返回标志true
        if(rightFlg==true){
            return true;
        }
        //程序全部执行完毕，说明未找到路径，将当前根节点弹出并返回标志false
        stack.pop();
        return false;
    }
}
